package com.linchong.binarysearch.easy;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-28 21:17
 * @Description: MountainSequence$
 * 1,2,4,5,3,2,1
 * 寻找峰顶值，利用单调性
 * A.length >= 3
 * 存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/peak-index-in-a-mountain-array
 *
 */
public class MountainSequence {
	public int peakIndexInMountainArray(int[] arr) {
		int start = 1,end = arr.length-1;

		while (start+1<end){
			int mid = start+(end-start)/2;
			if(arr[mid]>arr[mid-1]){
				start = mid;
			}else{
				end = mid;
			}
		}

		if(arr[start]<arr[end]){
			return end;
		}else{
			return start;
		}
	}

	public static void main(String[] args) {
		int[] nums = {0,2,4,8,9,7,1,0};
		MountainSequence instance = new MountainSequence();
		System.out.println(instance.peakIndexInMountainArray(nums));
	}

}


















